The present invention relates generally to two- and three-dimensional mesh shapes and, more particularly, to the simplification of the meshes on the surfaces of such shapes.
Many applications, such as medical and industrial design and manufacturing applications, involve manipulating and editing a digital model of an object. As one skilled in the art will understand, such a digital model may be created by scanning an object to create a point cloud representation of the object. The surface of such a model of a scanned object typically consists of a plurality of points, the number of which is a function of the resolution of the scanning process. Once such a point cloud representation has been obtained, the surface of the object may then be approximated by connecting the points of the point cloud to form a plurality of geometric shapes, such as triangles, on the surface of the model. This model may then, for example, be edited by using computer aided design (CAD) software programs or similar specialized image manipulation software programs.
FIG. 1 shows an illustrative model of the surface 101 of such an object. Referring to that figure, points 103 are, illustratively, the points in a point cloud that are obtained from the scanning of the object. Then, as discussed above, well-known methods are used to connect the points in a way such that the surface of the object is approximated by a plurality of triangles 102, referred to herein collectively as a triangle mesh. One such method for constructing a surface by connecting points and forming triangles is described, for example, in F. Bernardini et al.,The Ball-Pivoting Algorithm for Surface Reconstruction, IEEE Transactions on Visualization and Computer Graphics, 5(4), October-December, 1999, pp. 349-359, which is hereby incorporated by reference herein in its entirety. Many other methods for creating mesh surfaces have also been developed and are well-known.
As one skilled in the art will recognize, there is an inherent tradeoff between the accuracy of the approximation of a surface and the complexity of the triangle mesh used for the approximation. Specifically, a mesh consisting of a large number of relatively small triangles will typically produce a more accurate surface approximation. However, the larger the number of triangles, the greater the volume and complexity of the computations required to create and edit the surface. Therefore, as one skilled in the art will also recognize, it is thus advantageous to balance the complexity of the mesh surface with the computational cost to produce an accurate surface model while, at the same time, reducing the associated cost of creating and editing the model. To achieve such a balance, mesh simplification algorithms have been developed to simplify mesh models and, therefore, reduce the aforementioned computational costs while at the same time retaining satisfactory accuracy.
Prior attempts at simplifying a triangle mesh surface have involved either local or global methods, As one skilled in the art will recognize, local methods attempt to simplify a mesh by treating discrete portions of a mesh individually while, on the other hand, global methods attempt to simplify the mesh by treating the entire mesh as a whole. Global methods involve, for example, minimizing an error function that ranks all of the possible mesh simplification steps and then performs them, illustratively, in order according to the identified rank (i.e., starting with those steps that alter the geometry of the mesh the least). Given the larger number of triangles in meshes of complex objects, global methods require a relatively large number of computations to rank the simplification steps and then reconstruct a simplified mesh surface of a model. On the other hand, local methods require less computations since fewer points/triangles in a mesh are to be simplified at any one time. As one skilled in the art will recognize, local methods of mesh simplification are greedy algorithms in that they attempt to find a locally optimum choice (here, a mesh simplification choice) at each stage of the algorithm. The goal of such algorithms is to attempt to determine the global optimal solution to mesh simplification based on local results. Since local algorithms do not consider the entire set of triangles in the mesh, however, such a global optimal solution is typically not achieved. However, while such local algorithms typically do not result in the global optimal solution, they typically provide satisfactory approximations of such a solution. Therefore, since the computational cost of such local methods is typically much lower than global methods, and the results of such methods are adequate for most applications, many attempts at mesh simplification have relied on such local methods.
Different local mesh simplification methods are known. One class of such methods, known as vertex decimation methods, function by removing vertices of triangles and then reconstructing the surface of the model to fill in the resulting gap in the surface left by the deleted vertex. However, such methods can be undesirable since such surface reconstruction requires a reconstruction of the entire mesh surface once one or more vertices of local triangles have been deleted. Thus, the computational cost of such methods is relatively high.
Another local mesh simplification method, referred to herein as edge contraction, also functions to reduce the number of vertices in a mesh. Unlike the vertex decimation technique, the edge contraction method does not delete the vertices and, therefore, create gaps in the mesh that require reconstruction of the surface. Instead, such edge contraction methods operate by identifying a target edge to be contracted and, then, by moving one or both of the two endpoints of the target edge to a single position. According to this method, and as discussed further herein below, all edges incident to the original vertices of the contracted edge are thus linked at this single position Any triangle faces that have degenerated into lines or points are then removed.
FIGS. 2A and 2B show an example of how edge contraction can be used to simplify a 2D or 3D surface approximated by a triangle mesh. Specifically, referring to those figures, surface 201 is a surface of an object characterized by a mesh of triangles 202. Each of the triangles 202 is characterized by having three vertices and three edges connecting those vertices. As discussed above, during edge contraction, one edge, such as edge 203 between vertices 206 and 207, is contracted in a way such that vertex 206 and vertex 207 are moved to the same position. The result of such a contraction is shown in FIG. 2B. Specifically, edge 203 is contracted so that vertex 206 and vertex 207 are positioned at position 204 in FIG. 2B. As a result, triangle faces 212 and 213 are transformed into edges 218 and 219 in FIG. 2B. Also, all incident edges to vertices 206 and 207, such as edges 208, 209, 210 and 211, now meet at new vertex 204. Thus, the resulting mesh is simplified by the consolidation of two vertices into a single vertex and the removal of two triangle faces from the mesh surface.
A key determination in edge contraction operations is how to contract the edge into a single vertex and, more particularly, where vertex 204 should be positioned in the model after the contraction is completed. Typical prior efforts selected one of the vertices, such as vertex 206 in FIG. 2A, and then contracted edge 203 in a way such that the position of vertex 204, which combined vertices 206 and 207 together, was at the position of prior vertex 206. Alternatively, an average of the position of vertices 206 and 207 was determined and the new vertex 204 was positioned at that average position.